# 有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
#  例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，
#  但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
#  给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新
# 排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
#
#  示例 1：
# 输入：s = "25525511135"
# 输出：["255.255.11.135","255.255.111.35"]
#
#  示例 2：
# 输入：s = "0000"
# 输出：["0.0.0.0"]
#
#  示例 3：
# 输入：s = "101023"
# 输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
from typing import List


class Solution:
    def restoreIpAddresses2(self, s: str) -> List[str]:
        """
        将字符串分成4段，然后判断能否组成IP地址
        :param s:
        :return:
        """
        def check(string: str) -> bool:
            if (len(string) > 1 and string[0] == '0') or int(string) > 255:
                return False
            return True

        sLen = len(s)
        if sLen < 4 or sLen > 12:
            return []
        res = []
        for i in range(1, min(4, sLen - 2)):
            for j in range(i + 1, min(i + 4, sLen - 1)):
                for k in range(j + 1, min(j + 4, sLen)):
                    if sLen - k > 3:
                        continue
                    tmpAddress = [s[:i], s[i:j], s[j:k], s[k:]]
                    flag = True
                    for a in tmpAddress:
                        if not check(a):
                            flag = False
                            break
                    if flag:
                        res.append('.'.join(tmpAddress))
        return res

    def restoreIpAddresses1(self, s: str) -> List[str]:
        res = set()

        def check(string: str) -> bool:
            if len(string) == 0 or (len(string) > 1 and string[0] == '0') or int(string) > 255:
                return False
            return True

        def backTrack(needSolveStr: str, singleRes) -> None:
            if len(needSolveStr) == 0 and len(singleRes) == 4:  # 待处理的字符串为 '' 并且单个的结果集长度为4,就将结果保存到res中
                res.add('.'.join(singleRes))
            # 对后面不可能组成IP地址的情况进行剪枝
            if len(needSolveStr) < 4 - len(singleRes) or len(needSolveStr) > 3 * (4 - len(singleRes)):
                return
            for i in range(1, 4, 1):
                tmpStr = needSolveStr[0:i]
                if check(tmpStr):
                    singleRes.append(tmpStr)
                    backTrack(needSolveStr[i:], singleRes)
                    singleRes.pop()

        backTrack(s, [])
        return list(res)

    def restoreIpAddresses(self, s: str) -> List[str]:
        return self.restoreIpAddresses2(s)


if __name__ == "__main__":
    s = "101023"
    print(Solution().restoreIpAddresses(s))
